package Sort;

import java.util.Arrays;

public class Merge {
    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6,0};
        merge(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void merge(int[] arr,int l,int r){
        if(l >= r) return;
        int mid = l+r>>1;
        merge(arr,l,mid);
        merge(arr,mid+1,r);
        int i = l;
        int j = mid + 1;
        int[] temp = new int[r-l+1];
        int k = 0;
        while (i <= mid && j <= r){
            if (arr[i] < arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while (i <= mid){
            temp[k++] = arr[i++];
        }
        while (j <= r){
            temp[k++] = arr[j++];
        }
        for(i = l,j = 0;i<=r;i++,j++){
            arr[i] = temp[j];
        }
    }
}
